package com.atcumt.Carl.Stack;

import java.util.ArrayDeque;
import java.util.Stack;

public class Stack01 {

    /**
     * 有效的括号
     * 方法：栈先进后出，三种不匹配的情况全覆盖
     */
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(')');
            } else if (c == '[') {
                stack.push(']');
            } else if (c == '{') {
                stack.push('}');
            } else if (!stack.isEmpty() || c != stack.pop()) {
                return false;
            }
        }
        return stack.isEmpty();
    }

    /**
     * 删除字符串中所有相邻重复项
     * 方法：相同左元素 -> 左括号，相同右元素 -> 右括号
     */
    public String removeDuplicates(String s) {
        ArrayDeque<Character> deque = new ArrayDeque<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (deque.isEmpty() || deque.peek() != c) {
                deque.push(c);
            } else {
                deque.poll();
            }
        }

        String str = "";
        while (!deque.isEmpty()) {
            str = deque.pop() + str;
        }
        return str;
    }



    /**
     * 逆波兰表达式 后缀表达式，运算符写在后面
     * 方法：遇到数字入栈；遇到运算符取出栈顶两个数字进行计算，并将结果压入栈中
     * 正则表达式：\\-?\\d+ 是匹配一个或多个数字(0到9)的整数部分
     */
    public int evalRPN(String[] tokens) {
        ArrayDeque<String> deque = new ArrayDeque<>();

        for (String s : tokens) {
            if (s.matches("\\-?\\d+")) {
                deque.push(s); // 整数就压入栈
            } else {
                int y = Integer.parseInt(deque.pop());
                int x = Integer.parseInt(deque.pop());
                int res = 0;

                if (s.equals("+")) {
                    res = x + y;
                } else if (s.equals("-")) {
                    res = x - y;
                } else if (s.equals("*")) {
                    res = x * y;
                } else if (s.equals("/")) {
                    res = x / y;
                }

                deque.push("" + res);
            }
        }
        return Integer.parseInt(deque.pop()); // 最后栈顶元素为最终结果
    }

}
